//(c) Copyright 2012 Hewlett-Packard Development Company, L.P.
//
//Confidential computer software. Valid license from HP required for possession, use or copying.
//Consistent with FAR 12.211 and 12.212, Commercial Computer Software, Computer Software Documentation, 
//and Technical Data for Commercial Items are licensed to the U.S. Government under vendor's standard commercial license.

package com.algorithms;

import java.util.Stack;

public class BinaryTree {

	private int data;
	private BinaryTree left, right;

	//private BinaryTree parent;

	public BinaryTree(int data) {
		this.data = data;
		this.left = null;
		this.right = null;
	}

	private void insert(BinaryTree root, int data) {
		if (root.data >= data) {//小于等于根认为是左节点
			if (root.left == null) {
				root.left = new BinaryTree(data);
			} else {
				insert(root.left, data);
			}
		} else {//大于根认为是右节点
			if (root.right == null) {
				root.right = new BinaryTree(data);
			} else {
				insert(root.right, data);
			}
		}
	}

	public static BinaryTree build(int[] a) {
		BinaryTree root = new BinaryTree(a[0]);
		for (int i = 1; i < a.length; i++) {
			root.insert(root, a[i]);
		}
		return root;
	}

	/**
	 * 先根
	 * @param root
	 */
	public void preOrderVisit(BinaryTree root) {
		if (root != null) {
			System.out.print(root.data + " ");
			preOrderVisit(root.left);
			preOrderVisit(root.right);
		}
	}

	/**
	 * 先根,非递归实现
	 * @param root
	 */
	public void noRecursivePreOrderVisit(BinaryTree root) {
		Stack<BinaryTree> stack = new Stack<BinaryTree>();
		if (root != null) {
			stack.push(root);
			while (!stack.isEmpty()) {
				BinaryTree node = stack.pop();
				System.out.print(node.data + " ");
				if (node.left != null)
					stack.push(node.left);
				if (node.right != null)
					stack.push(node.right);
			}
		}
	}

	/**
	 * 中根
	 * @param root
	 */
	public void inOrderVisit(BinaryTree root) {
		if (root != null) {
			inOrderVisit(root.left);
			System.out.print(root.data + " ");
			inOrderVisit(root.right);
		}
	}

	/**
	 * 后根
	 * @param root
	 */
	public void postOrderVisit(BinaryTree root) {
		if (root != null) {
			postOrderVisit(root.left);
			postOrderVisit(root.right);
			System.out.print(root.data + " ");
		}
	}

	public static void main(String[] args) {
		int[] list = new int[] { 1, 2, 3 };
		BinaryTree bt = BinaryTree.build(list);
		System.out.print("\nPreOrder visited: ");
		bt.preOrderVisit(bt);

		System.out.print("\nNoRecursivePreOrderVisit visited: ");
		bt.noRecursivePreOrderVisit(bt);

		System.out.print("\nInOrder visited: ");
		bt.inOrderVisit(bt);
		System.out.print("\nPOrder visited: ");
		bt.postOrderVisit(bt);

	}

}
